package com.Oct_Twenty_One;

import java.util.Arrays;

/**
 * 684. 冗余连接
 * 树可以看成是一个连通且 无环 的 无向 图。
 *
 * 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
 *
 * 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/redundant-connection
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/22 00:22
 */

public class Solution684 {

    int[] fa=new int[1005];

    public int[] findRedundantConnection(int[][] edges) {
        init();
        for (int i=0;i<edges.length;i++)
        {
            if (Same(edges[i][0],edges[i][1])) return edges[i];
            else Join(edges[i][0],edges[i][1]);
        }
        return new int[]{};
    }
    
    void init(){
        for (int i = 0; i < fa.length; i++) {
            fa[i]=i;
        }
    }

    void Join(int u,int v){
       u=find(u);
       v=find(v);
       if (u==v) return;
       fa[v]=u;
    }

    int find(int u){
        return u==fa[u]?u:(fa[u]=find(fa[u]));
    }

    boolean Same(int u,int v){
        u=find(u);
        v=find(v);
        return u==v;
    }

    public static void main(String[] args) {
        Solution684 solution684=new Solution684();
        System.out.println(Arrays.toString(solution684.findRedundantConnection(new int[][]{{1, 2}, {1, 3}, {2, 3}})));
    }

}
